#include <iostream>
#include <vector>
#include "BinarySearchTree.h"
#define mode  0  //0为直接排序，1为乱序
#define scale 1000000  //样本空间大小
#define n 100 //重复运行次数
//c++乱序算法
#include<algorithm>
#include<ctime>
 
using namespace std;
double sum = 0; 
void BSTSorting(std::vector<int> &_arr, int _mode)
{
    if (_mode=0)
    {
        BinarySearchTree<int> bst;
        clock_t startTime = clock();   //测试程序的起始时间
        for(auto & i : _arr)//插入二叉树进行排序
            bst.insert(i);
        clock_t endTime = clock();    //测试程序的结束时间
    	//bst.printTree();      	//打印二叉树;   
        sum+= double(endTime - startTime) / CLOCKS_PER_SEC;
        bst.~BinarySearchTree();
    }
    else
    {
        BinarySearchTree<int> bst;
    
        //将数组_arr乱序
	    srand((unsigned int)time(0));
        clock_t startTime = clock(); //测试程序的起始时间
        random_shuffle(_arr.begin(), _arr.end());
        for(auto & i : _arr)
            bst.insert(i);
        clock_t endTime = clock();//测试程序的结束时间
    	//bst.printTree();   
        sum+= double(endTime - startTime) / CLOCKS_PER_SEC ;    
        bst.~BinarySearchTree();
    }
    
}
 
int main()
{
 
    vector<int> num;
 
    //------------------------------------------数组生成方式
	/*
    int x;
    while (cin >> x && x)//以0作为输入结束   
	{
		num.push_back(x);
	}
    */
    //NO1:采取自己输入数据的方式(此时建议将mode调为1)

    for (int i = 0; i < scale; i++)
    {
        num.push_back(i);
    }
    //NO2：生成一大串的数组

    //-----------------------------------------二叉搜索树排序
    for (int i = 0; i < n ; i++)    
	BSTSorting(num, mode);
    cout << "平均时间为" << sum/n << endl;
    

    //-----------------------------------------以下为测试程序
    /*
    //测试remove()
	for (size_t i=0; i < 5; ++i)
		bst.remove(i);
	bst.printTree();
    
    //测试conatains()
	cout << bst.contains(7) << endl;
 
	//测试最大最小值
	cout << "最大值： " << bst.findMax() << endl;
	cout << "最小值： " << bst.findMin() << endl;
 
	//测试拷贝构造函数
	BinarySearchTree<int> bst2(bst);
	bst2.printTree();
 
	//测试赋值操作
	BinarySearchTree<int> bst3;
	bst3 = bst2;
	bst3.printTree();
    */

	return 0;
}
